package com.seminar.pentago;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.io.FileWriter;
import java.io.BufferedWriter;

enum Stage {
    PLACEMENT, ROTATION
}

/**
 * A small class to store some information about the end of the game.
 * @author Andrew
 */
class PentagoWinningInformation {
    private static int[] winners = {0, 0, 0, 0};
    private static ArrayList<long[]> boards = new ArrayList<long[]>();
    private static ArrayList<Stage> stages = new ArrayList<Stage>();
    private static ArrayList<Integer> turns = new ArrayList<Integer>();
    
    public static synchronized void add(int thisWinner, long[] thisBoard, 
                           Stage thisStage, int thisTurns) {
        winners[thisWinner] += 1;
        boards.add(thisBoard);
        stages.add(thisStage);
        turns.add(thisTurns);
    }
    
    public static void add(int thisWinner) {
        winners[thisWinner] += 1;
    }
    
    public static int[] getWinners() {
        return winners;
    }
    
    public static ArrayList<long[]> getBoards() {
        return boards;
    }
    
    public static ArrayList<Stage> getStages() {
        return stages;
    }
    
    public static ArrayList<Integer> getTurns() {
        return turns;
    }
}

/**
 * A thread class for the Pentago Bitboard.
 * @author Andrew S. Hays
 */
class PentagoThread extends Thread {
    private int games;
    private int sides;
    private int numToCollect;
    /**
     * Constructor for running a set of games inside of a thread.
     * @param queue A list of data to append to.
     * @param games The number of games that are to be played.
     * @param sides The number of sides that are playing in this game.
     */
    public PentagoThread(int games, int sides, int numToCollect) {
        super();
        this.games = games;
        this.sides = sides;
        this.numToCollect = numToCollect;
    }
    
    /**
     * The "meat and potatoes" of the thread class.  It honestly doesn't do too
     * much, but this is where the thread magic happens anyways.
     */
    public void run() {
        PentagoBitboard.playRandomGames(games, sides, numToCollect);
    }
}

/**
 * The main class for creating a Pentago Bitboard.  This runs most of the games.
 * @author Andrew
 *
 */
public class PentagoBitboard {
    private long boards[];
    private int sides;
    private int turns;
    private int winner;
    private Stage stage;
    
    /**
     * This basically specifies what fields are in what quadrant.  It's 
     * static and hardcoded in for speed, since this never changes.
     */
    private static final int[][] fields = {{ 0, 1, 2, 6, 7, 8,12,13,14},
                                           {18,19,20,24,25,26,30,31,32},
                                           {21,22,23,27,28,29,33,34,35},
                                           { 3, 4, 5, 9,10,11,15,16,17}};
    
    /**
     * A hexadecimal representation of what a full bitboard looks like.
     */
    private static final long full = 0xfffffffffL;
    
    /**
     * A specification of what the rotation looks like in bit-shifts for 
     * rotating zero times, one time, two times, and three times 
     * (in the clockwise direction).
     */
    private static final int[][] rotations = 
                    {{  0,  0,  0,  0,  0,  0,  0,  0,  0},
                     {  2,  7, 12, -5,  0,  5,-12, -7, -2},
                     { 14, 12, 10,  2,  0, -2,-10,-12,-14},
                     { 12,  5, -2,  7,  0, -7,  2, -5,-12}};
    
    /**
     * A list of all the winning game board positions in the game.
     */
    private static final long[] wins = {0x1fL,0x3eL,0x7c0L,0xf80L,0x3e000L,
        0x1f000L,0x108421L,0x7c0000L,0xf80000L,0x4104104L,0x1041041L,0x1084204L,
        0x8208208L,0x2082082L,0x10204081L,0x82082080L,0x41041040L,0x8421000bL,
        0x3e000000L,0x1f000000L,0x10410410L,0x20408101L,0x20820820L,0x40108420L,
        0x820820800L,0x810204080L,0x410410400L,0x408102006L,0x208208200L,
        0x104104100L,0x7c0000000L,0xf80000000L};
    
    /**
     * Each number copies over all but one quadrant from the bitboard (for easy
     * rotation of the quadrant that was not copied).
     */
    private static final long[] quadcopy = 
                    {0xfffff8e38L, 0xe38e3ffffL, 0x1c71fffffL, 0xffffc71c7L};
    
    /**
     * A mapping for converting hexadecimal numbers to binary representation,
     * since Java doesn't seem to have a function to do so.
     */
    private static final Map<String,String> hexToBin;
    
    /**
     * A static initializer for said mapping.
     */
    static {
        Map<String,String> htbInit = new HashMap<String,String>();
        htbInit.put("0", "0000");
        htbInit.put("1", "0001");
        htbInit.put("2", "0010");
        htbInit.put("3", "0011");
        htbInit.put("4", "0100");
        htbInit.put("5", "0101");
        htbInit.put("6", "0110");
        htbInit.put("7", "0111");
        htbInit.put("8", "1000");
        htbInit.put("9", "1001");
        htbInit.put("a", "1010");
        htbInit.put("b", "1011");
        htbInit.put("c", "1100");
        htbInit.put("d", "1101");
        htbInit.put("e", "1110");
        htbInit.put("f", "1111");
        hexToBin = Collections.unmodifiableMap(htbInit);
    }
    
    /**
     * This function returns a copy of s repeated t times.
     * @param s The string to copy.
     * @param t How many times to copy the string.
     * @return The string copied t times.
     */
    public static String multiply(String s, int t) {
        String out = "";
        for (int i = 0; i < t; i++) {
            out += s;
        }
        return out;
    }
    
    /**
     * A constructor for the bitboard.
     * @param sides The number of players in the game.  Usually two.
     */
    public PentagoBitboard(int sides) {
        this.sides = sides;
        this.reset();
    }
    
    /**
     * A function for converting a number into a binary string.
     * @param num The 64-bit number to convert.
     * @return 
     */
    private static String toBinaryString(long num) {
        String hex = String.format("%09x", num);
        String outString = "";
        for (int i = 0; i < hex.length(); i++) {
            outString += hexToBin.get(""+hex.charAt(i));
        }
        return outString;
    }
    
    /**
     * Takes a string representation of a board, and turns it into a pretty 
     * board that is a 6x6 array of numbers (in string form, with newlines).
     * @param board The board as a string.
     * @return The board as a 6x6 string.
     */
    public static String printBoard(String board) {
        return board.replaceAll("(\\d{6})", "$1\n");
    }
    
    /**
     * Takes a long representation of a board, and turns it into a pretty board
     * that is a 6x6 array of numbers.
     * @param board
     * @return The board as a 6x6 string.
     */
    public static String printBoard(long board) {
        return printBoard(toBinaryString(board));
    }
    
    /**
     * Plays a number of random games in a threaded form, using the threaded 
     * class.  Note that these games may repeat.
     * @param count The number of games to play.
     * @param threads The number of threads to use.
     * @param sides The number of sides that are playing.
     * @return The statistics from the game.
     */
    public static void playRandomThreadedGames(int count, int threads,  
                                               int sides, int numToCollect) {
        final int gamesPerThread = count/threads;
        final int numToCollectPerThread = numToCollect/threads;
        ArrayList<Thread> al = new ArrayList<Thread>();
        Thread t;
        for (int i = 1; i < threads; i++) {
            t = new PentagoThread(gamesPerThread, sides, numToCollectPerThread);
            t.start();
            al.add(t);
        }
        playRandomGames(gamesPerThread, sides, numToCollectPerThread);
        try {
            for(Thread thr: al) {
                thr.join();
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    
    /**
     * Plays a number of games randomly.  Note that these games may repeat.
     * @param count The number of games to play.
     * @param sides The number of sides that are playing.
     * @return The statistics from the game.
     */
    public static void playRandomGames(int count, int sides, 
                                        int numToCollect) {
        PentagoBitboard p = new PentagoBitboard(sides);
        int collectAtEvery = numToCollect == 0 ? 0 : count/numToCollect;
        if (collectAtEvery == 0 && numToCollect != 0) { collectAtEvery = 1; }
        int[] data = new int[1 << sides];
        for (int i = 0; i < data.length; i++) { data[i] = 0; }
        for (int i = 0; i < count; i++) {
            p.finishGameRandomly();
            if (collectAtEvery != 0 && i % collectAtEvery == 0){
                PentagoWinningInformation.add(p.winner, p.boards, p.stage,
                                              p.turns);
                                                
            } else {
                PentagoWinningInformation.add(p.winner);
            }
            p.reset();
        }
        
    }
    
    /**
     * Print the current board of a specific player in a pretty format.
     * @param player The player's board to print.
     * @return The board as a string.
     */
    public String prettyPrint(int player) {
        if (player < 1) return null;
        return toBinaryString(this.boards[player]).
                    replaceAll("(\\d{6})", "$1\n");
    }
    
    /**
     * Print the current board for every player.  Note that player two is 
     * represented as 2, player three as 3, and so on.
     * @return The board as a string.
     */
    public String prettyPrint() {
        char[][] boards = new char[this.boards.length][36];
        for (int i = 1; i < boards.length; i++) {
            boards[i] = toBinaryString(this.boards[i]).replace("1", ""+i).
                                toCharArray(); 
        }
        for (int player = 2; player <= this.sides; player++) {
            for (int ch = 0; ch < boards[1].length; ch++) {
                if (boards[1][ch] == '0' && 
                    boards[player][ch] != '0') {
                    boards[1][ch] = boards[player][ch];
                }
            }
        }
        return new String(boards[1]).replaceAll("(\\d{6})", "$1\n");
    }
    
    /**
     * Reset everything back to the way it initializes.
     */
    public void reset() {
        this.boards = new long[this.sides+1];
        this.turns = 0;
        for(int i = 0; i < this.sides; i++) { this.boards[i] = 0L; }
    }
    
    /**
     * Plays a turn given the current player.
     * @param pos The position on the board to play in.
     * @param quadrant The quadrant to rotate (1-4).
     * @param direction The direction to rotate in. (Typically -1 or 1.)
     */
    public void playTurn(int pos, int quadrant, int direction) {
        this.playTurn(pos, quadrant, direction, this.turns%this.sides + 1);
    }
    
    /**
     * Plays a turn with a supplied player.
     * @param pos The position on the board to play in.
     * @param quadrant The quadrant to rotate (1-4).
     * @param direction The direction to rotate in. (Typically -1 or 1.)
     * @param player The player to play for. 
     */
    public void playTurn(int pos, int quadrant, int direction, int player) {
        stage = Stage.PLACEMENT;
        try {
            this.place(pos, player);
        } catch (Exception e) {
            e.printStackTrace();
        }
        if (this.isWon() == -1) {
            stage = Stage.ROTATION;
            this.rotate(quadrant, direction);     
        }
        this.turns += 1;
    }
    
    /**
     * Places a piece on the board for the given player.
     * @param pos The position to place in.
     * @param player The player to place for.
     * @throws ArrayIndexOutOfBoundsException If the space is already taken.
     */
    public void place(int pos, int player) throws 
                        ArrayIndexOutOfBoundsException {
        if (this.bittestAll(pos)) {
            throw new ArrayIndexOutOfBoundsException("This space has already "+
                                                     "been used.");
        }
        this.bitset(pos, player);
    }
    
    /**
     * Sets a given bit for a specific player.
     * @param pos The place to set the bit.
     * @param player The player to set the bit for.
     */
    private void bitset(int pos, int player) {
        this.boards[player] |= (1L << pos);
    }
    
    /**
     * Returns the value of a number given only that bit.
     * @param pos The position of the bit.
     * @param player The player to get the bit value of.
     * @return The value of the bit. (Not 1 or 0, but if the number
     * were 0b1100 and we were testing position 3, then the value would be
     * 0b100.)
     */
    private long getbit(int pos, int player) {
        return (1L << pos) & this.boards[player];
    }
    
    /**
     * Tests all the values of the bits to see if any are non-zero.
     * @param pos the position to test.
     * @return true if any value is non-zero.  Otherwise false.
     */
    private boolean bittestAll(int pos) {
        for (int i = 1; i <= this.sides; i++) {
            if (this.bittest(pos, i)) return true;
        }
        return false;
    }
    
    /**
     * Tests a specific player to see if the value is non-zero.
     * @param pos The position to test.
     * @param player The player to test.
     * @return true if any value is non-zero.  Otherwise false.
     */
    private boolean bittest(int pos, int player) {
        return ((1L << pos)&this.boards[player])>>pos == 1;
    }
    
    /**
     * Rotates a quadrant a given number of times (for all players).  Note that
     * both values are taken modulo 4. 
     * @param quadrant The quadrant to rotate.
     * @param times The number of times to rotate it.
     */
    public void rotate(int quadrant, int times) {
        times %= 4;
        if (times < 0) { times += 4; }
        if (times != 0) {
            quadrant %= 4;
            if (quadrant < 0) { quadrant += 4; }
            long[] boards = this.boards.clone();
            int[] rotation = rotations[times];
            int[] fieldList = fields[quadrant];
            
            for (int player = 1; player <= this.sides; player++) {
                boards[player] &= quadcopy[quadrant];
                for (int field = 0; field < 9; field++) {
                    if (rotation[field] < 0) {
                        boards[player] += 
                            (this.getbit(fieldList[field], player) >> 
                                        -rotation[field]);
                    } else {
                        boards[player] += 
                            (this.getbit(fieldList[field], player) <<  
                                         rotation[field]);
                    }
                }
            }
            this.boards = boards.clone();
        }
    }
    
    /**
     * Tests to see if the game is over.
     * @return -1 if the game is not over, 0 if it is a draw, and then some
     * combination of the players bits if the game was won my multiple people.
     */
    public int isWon() {
        int winner = 0;
        for (int player = 1; player <= this.sides; player++){
            for (int board = 0; board < 32; board++) {
                if((this.boards[player]&wins[board])==wins[board]) {
                    winner |= player;
                    break;
                }
            }
        }
        if (winner == 0 && this.turns < 35) return -1;
        this.winner = winner;
        return winner;
    }
    
    /**
     * Finishes the rest of the current game randomly.
     * @return The winner of the game.
     */
    public int finishGameRandomly() {
        int player = (this.turns % this.sides)+1;
        int pos = 0, quadrant = 0, direction = 0;
        Random r = new Random();
        ArrayList<Integer> empties;
        while (this.isWon() == -1) {                
            empties = this.getEmptiesAsArray();
            pos = empties.get(r.nextInt(empties.size()));
            quadrant = r.nextInt(4);
            direction = r.nextBoolean() ? 1 : -1;
            this.playTurn(pos, quadrant, direction, player);
            player = (this.turns % this.sides)+1;
        }
        return this.isWon();
    }
    
    /**
     * Gets all the empties as a 64-bit number, where if the bit is one, then
     * the space at that position is empty.
     * @return
     */
    public long getEmpties() {
        long board = 0;
        for (int i = 1; i <= this.sides; i++) {
            board |= this.boards[i];
        }
        return full&(~board);
    }
    
    /**
     * Returns the empty spaces as an ArrayList.
     * @return An ArrayList of Integers where each one is an empty position.
     */
    public ArrayList<Integer> getEmptiesAsArray() {
        long empties = this.getEmpties();
        
        ArrayList<Integer> al = new ArrayList<Integer>();
        for(int i = 0; i < 36; i++) {
            if (((1L << i)&empties) == (1L << i)) {
                al.add(i);
            }
        }
        return al;
    }
    
    /**
     * String conversion of the board.  Just calls prettyPrint().
     */
    public String toString() {
        return this.prettyPrint();
    }
    
    /**
     * What to run if this class is called from the command line.
     * @param args An array of arguments to pass to the function. \
     *   - arg[0]: How many games to play (Optional.)
     *   - arg[1]: How many of those games to collect data for (Optional.)
     * Note that arg[0] is required if you intend to supply arg[1]
     */
    public static void main(String... args) throws Exception {
        long t1, t2;
        int times = 100000;
        int timesToGetData = 100;
        if (args.length > 1) { timesToGetData = Integer.parseInt(args[1]); }
        if (args.length > 1) { times = Integer.parseInt(args[0]); }

        t1 = System.currentTimeMillis();
        PentagoBitboard.playRandomThreadedGames(times, 4, 2, timesToGetData); // to thread
        //PentagoBitboard.playRandomGames(times, 2, timesToGetData); // not threaded
        t2 = System.currentTimeMillis();
        int[] winners = PentagoWinningInformation.getWinners();
        BufferedWriter bw = new BufferedWriter(new FileWriter("outdata.txt"));
        ArrayList<long[]> boards = PentagoWinningInformation.getBoards();
        ArrayList<Integer> turns = PentagoWinningInformation.getTurns();
        ArrayList<Stage> stages  = PentagoWinningInformation.getStages();
        long[] boardsArray;
        for (int i = 0; i < boards.size(); i += times/timesToGetData) {
            boardsArray = boards.get(i);
            bw.write("" + boardsArray[1] + " " + boardsArray[2] + "\r\n");
            bw.write("" + stages.get(i) + "\r\n");
            bw.write("" + turns.get(i) + "\r\n");
        }
        for(int i = 0; i < winners.length; i++) {
            bw.write(String.format("%d: %d\r\n", i, winners[i]));
        }
        System.out.format("This operation took %fs", (t2-t1)/(1000.0));
        bw.close();
    }
}
